package com.cn.algorithm02.class21;

import lombok.AllArgsConstructor;
import lombok.Data;

import java.util.PriorityQueue;

/***
 * @author: hels
 * @description:
 *      给定一个咖啡机数组arr, arr[i]表示第i号咖啡机泡一杯咖啡的时间，每台咖啡机只能轮流泡咖啡；
 *      现在有n个人（人手一只杯子）等待咖啡机泡咖啡；
 *      只有一台洗杯子机器，一次只能洗一个杯子，时间耗费为a，洗完才能洗下一个；
 *      咖啡杯也可以自己挥发干净，耗费b时间，可以并行挥发；
 *      假设所有人拿到咖啡之后立即喝干净，返回每个人喝完咖啡等到所有咖啡机变干净的最短时间。
 *      四个参数：int[] arr, int n, int a, int b
 *
 *  解题思路：
 *      ①在不考虑咖啡清洗的情况下，求得N个人排队喝咖啡最短（佳）的排队时间数组int[] drinks；
 *          创建一个机器类Machine，属性开始工作时间点，泡咖啡时间；
 *          创建一个Machine小根堆来求drinks数组；
 *      ②给drinks数组加入a、b时间的影响，求得最小时间
 **/
public class C03_Coffe {
    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 8};
        int[] drinks = bestQueue(arr, 20);
        for (int i = 0; i < drinks.length; i++) {
            System.out.println(drinks[i]);
        }
        System.out.println(bestTime(drinks, 0, 3, 8, 0));
        System.out.println(bestTimeDp(drinks, 3, 8));
    }

    /**
     * 递归方法
     *
     * @param drinks    喝咖啡最佳排队方案
     * @param index     下标
     * @param wash      洗杯子时间
     * @param air       挥发时间
     * @param freePoint 咖啡机可用的空闲时间点
     * @return 最佳时间
     */
    public static int bestTime(int[] drinks, int index, int wash, int air, int freePoint) {
        if (index == drinks.length) {
            return 0;
        }

        // clean cup
        int cleanTime1 = Math.max(drinks[index], freePoint) + wash;
        int restTime1 = bestTime(drinks, index + 1, wash, air, cleanTime1);
        int t1 = Math.max(cleanTime1, restTime1);

        // 挥发 cup
        int cleanTime2 = drinks[index] + air;
        int restTime2 = bestTime(drinks, index + 1, wash, air, freePoint);
        int t2 = Math.max(cleanTime2, restTime2);

        return Math.min(t1, t2);
    }

    public static int bestTimeDp(int[] drinks, int wash, int air) {
        int maxFree = 0;
        int N = drinks.length;
        for (int i = 0; i < N; i++) {
            maxFree = Math.max(drinks[i], maxFree) + wash;
        }

        int[][] dp = new int[N + 1][maxFree + 1];
        // dp[N][。。。]  = 0
        for (int index = N - 1; index >= 0; index--) {
            for (int freePoint = 0; freePoint <= maxFree; freePoint++) {
                int cleanTime1 = Math.max(drinks[index], freePoint) + wash;
                if (cleanTime1 > maxFree) {
                    continue;
                }
                int restTime1 = dp[index + 1][cleanTime1];
                int t1 = Math.max(cleanTime1, restTime1);

                // 挥发 cup
                int cleanTime2 = drinks[index] + air;
                int restTime2 = dp[index + 1][freePoint];
                int t2 = Math.max(cleanTime2, restTime2);

                dp[index][freePoint] = Math.min(t1, t2);
            }
        }

        return dp[0][0];
    }

    /**
     * 获取最好的排队方案
     */
    public static int[] bestQueue(int[] arr, int n) {
        if (arr.length == 0) {
            return null;
        }
        PriorityQueue<Machine> pq = new PriorityQueue<>(((o1, o2) -> (o1.workPoint + o1.workTime) - (o2.workPoint + o2.workTime)));
        for (int i = 0; i < arr.length; i++) {
            Machine machine = new Machine(0, arr[i]);
            pq.add(machine);
        }
        int[] drinks = new int[n];
        for (int i = 0; i < n; i++) {
            Machine current = pq.poll();
            assert current != null;
            current.workPoint = current.workPoint + current.workTime;
            drinks[i] = current.workPoint;
            pq.add(current);
        }
        return drinks;
    }
}

@Data
@AllArgsConstructor
class Machine {
    int workPoint;
    int workTime;
}
